The Internet of Things (IoT) is widely and increasingly prevalent, which provides communication capabilities to various devices in the world to thereby allow the devices to perform remote measurements and realize the utilization of information collected from them. In the use of the IoT technology, there are needs for the development of technologies enabling more efficient management of vast amounts of information collected by various kinds of devices and faster search for desired information.
In order to manage vast amount of information with great efficiency, there is a technology called autonomous distributed key-value store (KVS), which stores information pieces (values), each associated with a single key used in search operations, in a distributed manner across a plurality of locations (nodes). In such an autonomous distributed KVS system, an algorithm such as a Distributed Hash Table (DHT) or a Skip Graph is used in order to uniquely determine a node responsible for storing key-value pairs to thereby allow a search for the value associated with a given key.
In Chord, a DHT-based implementation, for example, each node is assigned, based on predetermined rules, to one of a plurality of identifiers (ID's) set in advance, and each key is assigned to a node according to the node assignment to the individual identifiers. That is, the node assignment and key assignment made in association with a node entry to or exit from the autonomous distributed KVS system are determined autonomously. Therefore, the autonomous distributed KVS system supports straightforward addition and removal of nodes, thereby providing high scalability.
There is a proposed method of achieving data redundancy in a system for managing m-digit continuous numerical values in association with management key values by means of dividing the range of the continuous numerical values into a plurality of sections, creating as many replications of each pair of a management key and data as the number of sections, and storing the replications across a plurality of nodes. In addition, there is a proposed method of determining, in storing registration information pieces each including a key and original data of a data item corresponding to the key in DHT nodes, the order of the registration information pieces according to hash values of the keys and determining registration information pieces to be stored in the same node based on the determined order. Further, there is a proposed method where a single master node distributes identifiers uniquely associated with individual data pieces to slave nodes.
International Publication Pamphlet No. WO 2013027784
Japanese Laid-open Patent Publication No. 2011-198199
Japanese Laid-open Patent Publication No. 2009-20757
Japanese Laid-open Patent Publication No. 2012-178025
David Karger et al., “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (STOC '97), May 1997
In an autonomous distributed KVS system, key-value (KV) pairs stored in a node are lost as the node exits. Therefore, the autonomous distributed KVS system replicates key-value pairs and stores the copies in a plurality of nodes, as in the above-mentioned proposed technique of Karger et al., to thereby prevent the loss of the key-value pairs. However, frequent node entries and exits involve frequent replication of key-value pairs to different nodes, thus resulting in high communication load between nodes (inter-node communication load).
In addition, each node entry or exit entails an update of information used for node searching. Therefore, frequent node entries and exits lead to high processing load of nodes. For these reasons, in the case where, for example, mobile terminals likely to frequently enter and exit a system serve as nodes, the inter-node communication load and the processing load of nodes may be increased, which is likely to result in decreased performance of the system.